package sliding_window

/*
给定两个字符串s和 p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例1:
输入: s = "cbaebabacd", t = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:
输入: s = "abab", t = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
*/

func findAnagrams(s string, t string) []int {
	//初始化窗口
	need, window := make(map[byte]int), make(map[byte]int)
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}
	//双指针及有效判断值
	left, right, valid := 0, 0, 0
	var result []int

	//通过右指针循环s字符串
	for right < len(s) {
		//往窗口中放入数据
		c := s[right]
		//右移窗口
		right++
		//进行窗口数据的更新
		if _, ok := need[c]; ok {
			window[c]++ //更新窗口数据个数,可能重复
			//如果有效值的个数相同,更新有效值
			if window[c] == need[c] {
				valid++
			}
		}

		//收缩窗口 使用一个固定长度为len(t)的滑动窗口来维护
		for right-left >= len(t) {
			//如果找到合法的排列
			if valid == len(need) {
				//把下标放入结果集
				result = append(result, left)
			}

			//进行收缩，把值移出窗口
			d := s[left]
			left++

			//收缩窗口 不断寻找可行解，以至得到最优解
			if _, ok := need[d]; ok {
				if window[d] == need[d] {
					valid--
				}
				window[d]--
			}

		}

	}
	return result
}
